﻿#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<stdlib.h>
//typedef char DataType;
////定义节点 
//typedef struct TreeNode
//{
//    DataType val;
//    struct TreeNode* left;
//    struct TreeNode* right;
//}Node;
//
////建立一个节点
//Node* BuyNode(DataType x)
//{
//    Node* tmp = (Node*)malloc(sizeof(Node));
//    if (tmp == NULL)
//    {
//        perror("malloc");
//        exit(-1);
//    }
//    tmp->left = NULL;
//    tmp->right = NULL;
//    tmp->val = x;
//    return tmp;
//}
//
//Node* MakeTree()
//{
//    Node* root = BuyNode(' ');//先创建头结点
//    Node* na = BuyNode('A');
//    Node* nb = BuyNode('B');
//    Node* nc = BuyNode('C');
//    Node* nd = BuyNode('D');
//    Node* ne = BuyNode('E');
//    Node* nf = BuyNode('F');
//    Node* ng = BuyNode('G');
//    //建立树
//    root->left = na;
//
//    na->left = nb;
//    na->right = nc;
//
//    nb->left = nd;
//
//    nc->left = ne;
//    nc->right = nf;
//
//    nd->right = ng;
//
//    return root;
//}
////打印二叉树
//void PrintTree(Node* root, int n)
//{
//    if (root == NULL)
//        return;
//    PrintTree(root->right, n + 1);//遍历打印右子树
//    //访问根节点
//    for (int i = 0; i < n - 1; i++)
//    {
//        printf(" ");
//    }
//    if (n > 0)
//    {
//        printf("---");
//        printf("%c\n", root->val);
//    }
//    PrintTree(root->left, n + 1);//遍历打印左子树
//}
//
////前序遍历
//void PreOrder(Node* root)
//{
//    if (root == NULL)
//        return;
//    printf("%c", root->val);
//    PreOrder(root->left);
//    PreOrder(root->right);
//}
////中序遍历
//void InOrder(Node* root)
//{
//    if (root == NULL)
//        return;
//    InOrder(root->left);
//    printf("%c", root->val);
//    InOrder(root->right);
//}
////后序遍历
//void PostOrder(Node* root)
//{
//    if (root == NULL)
//        return;
//    PostOrder(root->left);
//    PostOrder(root->right);
//    printf("%c", root->val);
//}
//
////在树中查找元素
//Node* FindNode(Node* root, DataType x)
//{
//    if (root == NULL)
//        return NULL;
//    if (root->val == x)
//        return root;
//    Node* ret = FindNode(root->left, x);
//    if (ret)
//        return ret;
//    return FindNode(root->right, x);
//}
//
//int main()
//{
//    //先定义一个头结点
//    Node* root = MakeTree();
//    PrintTree(root, 0);//打印整棵树
//    //遍历
//    printf("前序遍历:");
//    PreOrder(root->left);
//    printf("\n中序遍历:");
//    InOrder(root->left);
//    printf("\n后序遍历:");
//    PostOrder(root->left);
//    //在树中查找元素
//    char ch;
//    printf("\n输入要查找的元素:");
//    scanf("%c", &ch);
//    Node* ret = FindNode(root->left, ch);
//    if (ret)
//        printf("元素%c在树中", ret->val);
//    else
//        printf("元素%c不在树中", ch);
//    return 0;
//}

#include <iostream>
#include <queue>
using namespace std;

typedef int DataType;
typedef struct TreeNode
{
    DataType val;
    struct TreeNode* left;
    struct TreeNode* right;
} Node;

Node* BuyNode(DataType x)
{
    Node* tmp = (Node*)malloc(sizeof(Node));
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    tmp->left = NULL;
    tmp->right = NULL;
    tmp->val = x;
    return tmp;
}
void PrintTree(Node* root, int n)
{
    if (root == NULL)
        return;
    PrintTree(root->right, n + 1);//遍历打印右子树
    //访问根节点
    for (int i = 0; i < n - 1; i++)
    {
        printf("   ");
    }
    if (n > 0)
    {
        printf("---");
        printf("%d\n", root->val);
    }
    PrintTree(root->left, n + 1);//遍历打印左子树
}
// 创建一个完全二叉树
Node* MakeCompleteBinaryTree()
{
    Node* n1 = BuyNode(1);
    Node* n2 = BuyNode(2);
    Node* n3 = BuyNode(3);
    Node* n4 = BuyNode(4);
    Node* n5 = BuyNode(5);
    Node* n6 = BuyNode(6);
    Node* n7 = BuyNode(7);

    n1->left = n2;
    n1->right = n3;

    n2->left = n4;
    n2->right = n5;

    n3->left = n6;
    n3->right = n7;

    return n1;
}
Node* MakeInCompleteBinaryTree()
{
    Node* n1 = BuyNode(1);
    Node* n2 = BuyNode(2);
    Node* n3 = BuyNode(3);
    Node* n4 = BuyNode(4);
    Node* n5 = BuyNode(5);
    Node* n6 = BuyNode(6);
    Node* n7 = BuyNode(7);

    n1->left = n2;
    n1->right = n3;

    n2->left = n4;
    n2->right = n5;

    n3->left = n6;
    n4->right = n7;

    return n1;
}

// 判断该二叉树是否为完全二叉树
bool IsBinaryTreeComplete(Node* root)
{
    queue<Node*>que;
    que.push(root);
    while (!que.empty())
    {
        if (que.front())//当没有看到空结点时
        {
            que.push(que.front()->left);
            que.push(que.front()->right);
            que.pop();
        }
        else//当发现空结点时
        {
            while (!que.empty())
            {
                if (que.front() != NULL)
                    return false;
                que.pop();
            }
        }
    }
    return true;
}

int main()
{
    Node* root = MakeCompleteBinaryTree();
    PrintTree(root,1);
    if (IsBinaryTreeComplete(root))
    {
        printf("是完全二叉树\n");
    }
    else
    {
        printf("不是完全二叉树\n");
    }
    root = MakeInCompleteBinaryTree();
    PrintTree(root, 1);
    if (IsBinaryTreeComplete(root))
    {
        printf("是完全二叉树\n");
    }
    else
    {
        printf("不是完全二叉树\n");
    }
    return 0;
}
